package com.zql.JianZhiOffer;

/**
 * Created By ShuHua on 2022/5/3.
 */
public class Offer_15 {

    /**
     * 使用与运算和无符号右移
     * 时间复杂度O(log2N) 空间复杂度O(1)
     * @param n
     * @return
     */
    public int hammingWeight(int n) {
        int res =0;
        while (n!=0){
            res+=(n&1);
            n=n>>>1;
        }
        return res;
    }

    /**
     * 利用 n&(n-1)每运算一次将最右边的1变成0
     * 时间复杂度O(M)m表示二进制位中1的个数
     * 空间复杂度O(1)；使用了res常量
     * @param n
     * @return
     */
    public int hammingWeight2(int n) {
        int res =0;
        while (n!=0){
            n=n&(n-1);
            res++;
        }
        return res;
    }
}
